//Given two strings s and t, return true if they are equal when both are typed 
//into empty text editors. '#' means a backspace character. 
//
// Note that after backspacing an empty text, the text will continue empty. 
//
// 
// Example 1: 
//
// 
//Input: s = "ab#c", t = "ad#c"
//Output: true
//Explanation: Both s and t become "ac".
// 
//
// Example 2: 
//
// 
//Input: s = "ab##", t = "c#d#"
//Output: true
//Explanation: Both s and t become "".
// 
//
// Example 3: 
//
// 
//Input: s = "a#c", t = "b"
//Output: false
//Explanation: s becomes "c" while t becomes "b".
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length, t.length <= 200 
// s and t only contain lowercase letters and '#' characters. 
// 
//
// 
// Follow up: Can you solve it in O(n) time and O(1) space? 
// Related Topics Two Pointers String Stack Simulation 👍 3318 👎 153


package leetcode.editor.en;

public class _844_BackspaceStringCompare {
    public static void main(String[] args) {
        Solution solution = new _844_BackspaceStringCompare().new Solution();
        boolean b = solution.backspaceCompare("as#c", "ab#c");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean backspaceCompare1(String s, String t) {
            int sIdx = s.length()-1, tIdx = t.length()-1;
            int sSkip = 0, tSkip = 0;
            while (sIdx >= 0 || tIdx >= 0) {
                while (sIdx>=0){
                    if (s.charAt(sIdx) == '#'){
                        sIdx--;
                        sSkip++;
                    }else if (sSkip>0){
                        sIdx--;
                        sSkip--;
                    }else {
                        break;
                    }
                }
                while (tIdx>=0){
                    if (t.charAt(tIdx) == '#'){
                        tIdx--;
                        tSkip++;
                    }else if (tSkip>0){
                        tIdx--;
                        tSkip--;
                    }else {
                        break;
                    }
                }

                if (tIdx>=0 && sIdx>=0){
                    if (t.charAt(tIdx) != s.charAt(sIdx)){
                        return false;
                    }
                }else {
                    if (tIdx>=0||sIdx>=0){
                        return false;
                    }
                }
                sIdx--;
                tIdx--;
            }
            return true;
        }














        public boolean backspaceCompare(String s, String t) {
            int sIdx = s.length() - 1, tIdx = t.length() - 1;
            int sSkip = 0, tSkip = 0;
            while (sIdx >= 0 || tIdx >= 0) {
                while (sIdx>=0){
                    if (s.charAt(sIdx) =='#') {
                        sSkip++;
                        sIdx--;
                    }else if(sSkip > 0){
                        sSkip--;
                        sIdx--;
                    }else {
                        break;
                    }
                }

                while (tIdx>=0){
                    if (t.charAt(tIdx) =='#') {
                        tSkip++;
                        tIdx--;
                    }else if(tSkip > 0){
                        tSkip--;
                        tIdx--;
                    }else {
                        break;
                    }
                }
                if (tIdx>=0 && sIdx>=0){
                    if (s.charAt(sIdx) != t.charAt(tIdx)){
                        return false;
                    }
                }else {
                    if (tIdx>=0 || sIdx>=0){
                        return false;
                    }
                }
                tIdx--;
                sIdx--;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}